﻿
P9244[蓝桥杯 2023 省 B] 子串简写


程序猿圈子里正在流行一种很新的简写方法：对于一个字符串，只保留首尾字符，将首尾字符之间的所有字符用这部分的长度代替。例如 internationalization 简写成 i18n，Kubernetes（注意连字符不是字符串的一部分）简写成 K8s，Lanqiao 简写成 L5o 等。

在本题中，我们规定长度大于等于 K 的字符串都可以采用这种简写方法(长度小于 K 的字符串不配使用这种简写)。

给定一个字符串 S 和两个字符 c
1
​
和 c
2
​
，请你计算 S 有多少个以 c
1
​
开头 c
2
​
结尾的子串可以采用这种简写？

输入格式
第一行包含一个整数 K。

第二行包含一个字符串 S 和两个字符 c
1
​
和 c
2
​
。

输出格式
一个整数代表答案。

输入输出样例
输入 #1复制
4
abababdb a b
输出 #1复制
6
说明 / 提示
【样例说明】

符合条件的子串如下所示，中括号内是该子串：

[abab]abdb
[ababab]db
[abababdb]
ab[abab]db
ab[ababdb]
abab[abdb]
【评测用例规模与约定】

对于 20 % 的数据，2≤K≤∣S∣≤10
4
。

对于 100 % 的数据，2≤K≤∣S∣≤5×10
5
。S 只包含小写字母。c
1
​
和 c
2
​
都是小写字母。

∣S∣ 代表字符串 S 的长度。

蓝桥杯 2023 省赛 B 组 G 题。


#include<bits/stdc++.h>
using namespace std;
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)
using ll = long long;
ll ans = 0;
//二分：重点看b；然后符合一定条件就去前面找刚好卡在边界的a；然后这个a左边所有的a都是符合条件的；累加情况即可！
int main() {
    IOS;
    ll k;
    cin >> k;
    string s;
    cin >> s;
    char a, b;
    cin >> a >> b;
    vector<ll> v;
    for (int i = 0; i < s.size(); i++) {
        if (s[i] == a)v.push_back(i);
        if (s[i] == b && v.size() != 0 && i - k + 1 >= 0) {//提前判断
            ll l = 0, r = (ll)v.size() - 1;
            while (l < r) {
                ll mid = (l + r + 1) >> 1;

                if (v[mid] <= i - k + 1) l = mid;
                else r = mid - 1;
            }
            //符合条件也可能找不到比如b虽然满足了；且数组有a；但是ab距离特别近不满足k:dcbacb
            if (v[l] <= i - k + 1)ans = ans + l + 1;
        }
    }
    cout << ans << '\n';
    return 0;
}



解法二：双指针：

思路：已知j如果位于数组的前k个是没有意义的；因此可以维护一段为k的区间在数组中移动即可；右区间值如果是b；
那么就找左区间端点的左边的a即可；左边一直统计a的个数
void solve(void) {
    int k; string s; char c1, c2;
    cin >> k >> s >> c1 >> c2;
    int ans = 0, cnt = 0;
    s = " " + s;
    for (int i = 1, j = k; j <= s.length(); i++, j++) {
        if (s[i] == c1) cnt++;
        if (s[j] == c2) ans += cnt;
    }
    cout << ans << endl;
}

